\section{Algebra} \label{sec:podstawy-algebry}
Rozdział zawiera opis podstaw algebry \cite{algebra}, których znajomość zakładam w rozdziale \ref{chap:wykonanie}.
\subsection{Relacja}
Relacja to dowolny podzbiór iloczynu kartezjańskiego skończonej liczby zbiorów.
Relacja dwuargumentowa to podzbiór iloczynu kartezjańskiego dwóch zbiorów ($A$ i $B$)
\[ R \subseteq A \times B \]
Należenie elementów do relacji \(\left( (a,b) \in R \right)\) zapisuje się śród-rostkowo  \(\left( aRb \right)\).
\subsubsection{Relacja równoważności} \label{subsec:equivalence-relation}
Relacja równoważności to relacja określona na zbiorze $A$ (tzn \(R \subseteq A \times A\))  która jest zwrota, symetryczna i przechodnia.
\begin{center}
  \begin{tabular}{l  l}
    zwrotność: & \begin{math} \label{eq:eqv-refl} \forall a \in A : aRa \end{math}\\
    symetryczność: & \begin{math} \label{eq:eqv-sym}\forall a,b \in A : aRb \implies bRa \end{math}\\
    przechodniość: & \begin{math} \label{eq:eqv-trans} \forall a,b,c \in A : aRb \land bRc \implies aRc \end{math}
  \end{tabular}
\end{center}
\subsection{Podstawowe struktury}
Niech $A$ będzie zbiorem z określoną na nim relacją równoważności ($\approx$). Niech \(\left( \cdot : A \times A \rightarrow A \right)\) będzie działaniem wewnętrznym w $A$, które zachowuje przystawanie względem relacji równoważności, tzn:
\begin{equation} \label{eq:cong-2}
  \forall x_1,x_2,y_1,y_2,z_1,z_2 \in A : \left(x_1 \cdot y_1 \approx z_1  \right) \land \left( x_2 \cdot y_2 \approx z_2 \right) \implies \left(x_1 \cdot y_1  \right) \cdot \left( x_2 \cdot y_2 \right) \approx z_1 \cdot z_2
\end{equation}
Nakładając dodatkowe warunki na $\cdot$, struktura $(A,\approx,\cdot)$ nazywa się:
\begin{center}
  \begin{tabular}{|l | c | c | c | c | }
    \hline 
    nazwa \textbackslash warunek & łączne & el. neutralny & el. odwrotny & przemienność \\
    \hline
    półgrupa & \ok & & & \\
    monoid & \ok & \ok & & \\
    grupa & \ok & \ok & \ok & \\
    gr. abelowa & \ok & \ok & \ok & \ok \\
    \hline
  \end{tabular}
\end{center}
Warunki:
\begin{center}
  \begin{tabular}{l  l}
    łączność: & \begin{math} \label{eq:assoc} \forall x,y,z \in A : (x \cdot y) \cdot z \approx x \cdot (y \cdot z) \end{math} \\
    element neutralny: & \begin{math} \label{eq:neutral-el} \exists \epsilon \in A : \forall x \in A : \epsilon \cdot x \approx x \land x \cdot \epsilon \approx x \end{math} \\
    element odwrotny: & \begin{math} \label{eq:inv-el} \forall x \in A : \exists x^{-1} \in A : x \cdot x^{-1} \approx \epsilon \land  x^{-1} \cdot x \approx \epsilon  \end{math} \\
    przemienność: & \begin{math} \label{eq:abelian} \forall x,y \in A : x \cdot y \approx y \cdot x \end{math}
  \end{tabular}
\end{center}
    
\subsubsection{Pierścień i ciało} \label{subsubsection:ring-field}
Pierścień to krotka \(\left(A,\approx,+,\cdot,0,1,- \right)\), gdzie \((A,\approx,+,0, -)\) jest grupą abelową (nazywana grupą addytywną), a \((A,\approx,\cdot,1)\) jest monoidem (nazywany monoidem multiplikatywnym). Dodatkowo, działanie multiplikatywne jest rozdzielne względem działania addytywnego:
\begin{gather*}
  \forall a, b, c \in A : a \cdot (b + c) \approx (a \cdot b) + (a \cdot c) \\
  \forall a, b, c \in A : (b + c) \cdot a \approx (b \cdot a) + (c \cdot a)
\end{gather*}
Pierścień przemienny to pierścień w którym działanie monoidu multiplikatywnego jest przemienne \(\left( \forall a,b \in A: x \cdot y \approx y \cdot x\right)\).
Ciało \( F  = \left(A,\approx,+,\cdot,0,1,-,^{-1} \right)\) to pierścień przemienny w którym każdy niezerowy element jest odwracalny, czyli \(\left( \forall x \in A\setminus\{0\} : \exists x^{-1} \in A : x \cdot x^{-1} \approx 1 \land  x^{-1} \cdot x \approx 1 \right)\), oraz $0 \not\approx 1$. 

\subsection{Homomorfizmy} \label{subsec:homomorfizmy}
Homomorfizmy to odwzorowania między strukturami które zachowują operacje.
Homomorfizm $f$ między półgrupami \((A_1,\approx_1,\cdot_1)\) i \((A_2,\approx_2,\cdot_2)\) to odwzorowanie które:
\begin{itemize}
\item zachowuje operację \begin{math} \forall x,y \in A_1 : f(x \cdot_1 y) \approx_2 f(x) \cdot_2 f(y) \end{math},
\item zachowuje przystawanie \begin{math} \forall x,y \in A_1 : x \approx_1 y \implies f(x) \approx_2 f(y) \end{math}.
\end{itemize}
Homomorfizm między monoidami \((A_1,\approx_1,\cdot_1,\epsilon_1)\) i \((A_2,\approx_2,\cdot_2,\epsilon_2)\) to homomorfizm między półgrupami, który odwzorowuje element neutralny w element neutralny: \( \left( f(\epsilon_1) \approx_2 \epsilon_2\right)\).
Homomorfizm między grupami to homomorfizm między monoidami (własności homomorfizmu między monoidami wystarczą żeby homomorfizm zachowywał odwracanie elementów, to znaczy żeby \( \forall x \in A_1 : f(x^{-1_1}) \approx_2 f(x)^{-1_2} \)).

\subsubsection{Jądro homomorfizmu} \label{subsubsec:kern}
Jądro homomorfizmu to zbiór elementów które przechodzą w element neutralny:
\[ \ker(f) = \{x | x \in A_1  \land f(x) \approx_2 \epsilon_2 \}\]
